//https://leetcode.cn/problems/palindromic-substrings/

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), ans = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = i; j < n; j++)
            {
                if(s[i] == s[j])
                {
                    if(i == j || i == j - 1)
                    {
                        dp[i][j] = true;
                        
                    }
                    else
                    {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                else
                {
                    dp[i][j] = false;
                }
                if(dp[i][j]) ++ans;
            }
        }
        return ans;
    }
};